package com.company.LinkList.ListDemo;

import com.company.LinkList.LIstTest;
import javafx.scene.Node;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}15:33
 */
public class Demo {
    public void Reverselteratively(ListNode head){
        ListNode pReversedHead = head;
        ListNode pNode = head;
        ListNode pPrev = null;
        while (pNode != null){
            ListNode pNext = pNode.next;
            if (pNext == null){
                pReversedHead = pNode;
            }
            pNode.next = pPrev;
            pPrev = pNode;
            pNode = pNext;
        }
    }

    //寻找链表中的中间节点 使用快慢指针
    public ListNode SearchMid(ListNode head){
        ListNode p = head;
        ListNode q = head;
        while (p != null && p.next != null && p.next.next!=null){
            p = p.next.next;
            q = q.next;
        }
        return q;
    }

    //检测链表是否有环 快慢指针
    public boolean isLoop(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        if (fast == null){
            return false;
        }
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }

    //寻找环链表入口
    public ListNode FindLoopPort(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next == null){
            return null;
        }
        slow = head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    //判断两个链表是否相交
    //方法一：
    public boolean isIntersect(ListNode h1,ListNode h2){
        if (h1 == null || h2 == null){
            return false;
        }
        ListNode tail = h1;
        //找到链表h1的最后一个节点
        while (tail.next != null){
            tail = tail.next;
        }
        ListNode tail2 = h2;
        while (tail2.next != null){
            tail2 = tail2.next;
        }
        if (tail == tail2){
            return true;
        }
        return false;
    }
    //方法二找到相交节点
    public static ListNode getFirstMeetNode(ListNode h1,ListNode h2){
        if (h1 == null || h2 == null){
            return  null;
        }
        ListNode tail = h1;
        int len1 = 1;
        //找到链表h1的最后一个节点
        while (tail.next != null){
            tail = tail.next;
            len1++;
        }
        ListNode tail2 = h2;
        int len2 = 1;
        //找到链表h2的最后一个节点
        while (tail2.next != null){
            tail2 = tail2.next;
            len2++;
        }
        //两个链表不相交
        if (tail != tail2){
            return null;
        }
        ListNode t1 = h1;
        ListNode t2 = h2;
        //找出较长的链表，先遍历
        if (len1 > len2){
            int d = len1 - len2;
            while (d != 0){
                t1 = t1.next;
                d--;
            }
        }else {
            int d = len2 - len1;
            while (d != 0){
                t2 = t2.next;
                d--;
            }
        }
        while (t1 != t2){
            t1 = t1.next;
            t2 = t2.next;
        }
        return t1;
    }
}
